"""

"""
from mode import *


class Solution:
    def maxTaxiEarnings(self, n: int, rides: List[List[int]]) -> int:
        dp = [0 for _ in range(n+1)]
        dist = defaultdict(list)
        for start, end, tip in rides:
            dist[end].append((start, end, tip))
        print(dist)

        for pos in range(1, n + 1):
            dp[pos] = dp[pos-1]
            for start, end, tip in dist[pos]:
                dp[pos] = max(dp[pos], dp[start] + end - start + tip)
        return dp[-1]


class Solution1:
    def maxTaxiEarnings(self, n: int, rides: List[List[int]]) -> int:
        dp = [0] * (n + 1)
        dist = defaultdict(list)
        for st, ed, _ in rides:
            dist[ed].append((st, ed, _))

        for pos in range(1, n + 1):
            dp[pos] = dp[pos - 1]  # 一方面, 可不不接终点到 i 的客
            for st, ed, tip in dist[pos]:
                dp[pos] = max(dp[pos], dp[st] + ed - st + tip)  # 另一方面, 接终点到 i 的客

        return dp[-1]


if __name__ == "__main__":
    A = Solution()
    print(A.maxTaxiEarnings(n=5, rides=[[2, 5, 4], [1, 5, 1]]))
    print(A.maxTaxiEarnings(n=20, rides=[[1, 6, 1], [3, 10, 2], [10, 12, 3], [11, 12, 2], [12, 15, 2], [13, 18, 1]]))
    A = Solution1()
    print(A.maxTaxiEarnings(n=5, rides=[[2, 5, 4], [1, 5, 1]]))
    print(A.maxTaxiEarnings(n=20, rides=[[1, 6, 1], [3, 10, 2], [10, 12, 3], [11, 12, 2], [12, 15, 2], [13, 18, 1]]))
